package com.tgy.leetcode;

/**
 * @Author: tgy
 * @Date: 2020-11-26 11:54
 *
 * https://leetcode-cn.com/problems/palindrome-linked-list/
 */
public class _234_回文链表 {

    public boolean isPalindrome(ListNode head) {

        if (head == null) {

            return true;
        }

        if (head.next == null) {

            return true;
        }

        ListNode headNode = head;
        // 找到中间分界点
        ListNode middleNode = findMiddle(headNode);
        // 反转从中间开始的指针
        ListNode otherHead = reversal(middleNode);


        while (otherHead != null) {

            if (head.val != otherHead.val) {

                return false;
            }

            head = head.next;
            otherHead = otherHead.next;
        }

        return true;
    }

    private ListNode findMiddle(ListNode head) {

        /**
         * middle 走一步，head走两步
         */
        ListNode middleNode = head;
        while (head.next != null && head.next.next != null) {

            middleNode = middleNode.next;
            head = head.next.next;
        }
        return middleNode;
    }

    private ListNode reversal(ListNode middleNode) {

        ListNode preNode = null,curNode = middleNode.next, nextNode;

        while (curNode != null) {

            nextNode = curNode.next;
            curNode.next = preNode;
            preNode = curNode;
            curNode = nextNode;
        }

        return preNode;
    }
}
